package a;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class 每样无限凑和_全排列去重 {

    static int[] p;
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();

    public static void main(String[] args) {
        p = new int[]{1,2,5};

        int tS = 5, fi=0;
        qpl(tS,fi);
        System.out.println(res);
        System.out.println(minGeshu(tS));
    }

    //具体拿法List: 无限0起+去重=fi只向前（全0起才用去重）
    static void qpl(int tS,int fi) {
        if(tS<=0){
            if(tS==0) res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < p.length; i++) {
            if(i<fi)continue;
            tmp.add(p[i]);  qpl(tS-p[i],i);  tmp.remove(tmp.size()-1);
        }
    }

    //具体拿法个数:  这个100就爆了，必须用dp - 改回溯
    public int change(int tS, int[] coins) {
        int n=coins.length;
        int[][] dp=new int[n+1][tS+1];//+1因为我要取到真实数，不能[n]到n-1
        dp[0][0]=1;//使用0种货币，凑0元钱,也是一种方案

        for (int i=1;i<=n;i++) {
            int v=coins[i-1];
            for (int j=0;j<=tS;j++)
                for (int k=0;k*v<=j;k++)//最多拿k*v,要不就超出目标和tS(也就是j)了
                    dp[i][j]+=dp[i-1][j- k*v];
        }
        return dp[n][tS];
    }



    //done最小币数 + map过
    static int minGeshu(int tS) {
        if(tS<=0){
            if(tS==0)return 0;
            return 99999;
        }
        int lu=99999;//1条路径max
        for (int i = 0; i < p.length; i++) {
            if(tS<p[i])continue;
            lu = Math.min(lu,minGeshu(tS-p[i])+1);
        }
        return lu;
    }
}






















